---
title: "入门"
created: 2025-11-28
tags:
  - 算法
---

# 入门

## 题目 [入门](https://www.luogu.com.cn/problem/P1683)

![[image-b7744977.png]]

## 思路分析

![[image-af5a1a2d.png]]

一条路走到黑

确定一下以后写这类问题的规范

![[image-145e7299.png]]

x正方向为下 y正方向为右

dx[4]={-1,0,1,0};

dy[4]={0,1,0,-1};

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=30;
char g[N][N];
int n,m;
int res;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool st[N][N];

void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<0 || nx>=n || ny<0 || ny>=m)
			continue;
		if(g[nx][ny]!='.')
			continue;
		if(st[nx][ny])
			continue;
		st[nx][ny]=true;
		res++;
		dfs(nx,ny);
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>m>>n;
	for(int i=0;i<n;i++){
		cin>>g[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(g[i][j]=='@'){
				st[i][j]=true;
				res++;
				dfs(i,j);
			}
		}
	}
	cout<<res;
	return 0;
 }
```

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=30;
char g[N][N];
int n,m;
int res;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool st[N][N];

bool isVaild(int x,int y){
	return x>=0 && x<=n-1 && y>=0 && y<=m-1 && !st[x][y];
}

void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(isVaild(nx,ny) && g[nx][ny]=='.'){
			st[nx][ny]=true;
			res++;
			dfs(nx,ny);
            //该点只能走一次 不能回溯
		}
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>m>>n;
	for(int i=0;i<n;i++){
		cin>>g[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(g[i][j]=='@'){
				st[i][j]=true;
				res++;
				dfs(i,j);
			}
		}
	}
	cout<<res;
	return 0;
 }
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/DFS BFS相关模型/DFS/简单图/4、方格分割|4、方格分割]] 🏠 [[00-刷题理模型]] ➡️ [[简单图|简单图]]